package com.lsa.the6046j.l5;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

import com.lsa.shenn.common.AbstractSorter;

public class RadixCountingSort extends AbstractSorter {
	public List<Integer> sort(List<Integer> l, int min) {
		List<Integer> result1 = new ArrayList<>(); // ArrayList with l.size elements
		result1.addAll(l);
		
		List<Integer> result2 = new ArrayList<>(); // ArrayList with l.size elements
		result2.addAll(l);

		int mask = 0xFF;
		
		List<Integer> result = result1;
		
		for (int pass = 0; pass < 4; pass++) {
			int[] freq = new int[256];
			for (int i = 0; i < l.size(); i++) {
				Integer e = l.get(i) - min;
				int idx = ((e & mask) >> (pass << 3));
				freq[idx]++;
			}
			
			for (int i = 1; i < freq.length; i++) {
				freq[i] += freq[i-1];
			}
			
			for (int i = l.size()-1; i > -1 ; --i) {
				Integer e = l.get(i) - min;
				int idx = ((e & mask) >> (pass << 3));
				result.set(freq[idx] - 1, e + min);
				freq[idx]--;
			}
			
			mask = mask << 8;
			l = result;
			if (pass % 2 == 0) {
				result = result2;
			}
			else {
				result = result1;
			}
		}
		
		return result;
	}
	
	@Override
	public List<Integer> sort(List<Integer> l) {
		if (l.isEmpty()) {
			return l;
		}
		return sort(l, Collections.min(l));
	}
}
